#include <iostream>
using namespace std;

size_t Left(size_t n)
{
	return n * 2 + 1;
}

size_t Right(size_t n)
{
	return n * 2 + 2;
}

size_t Parent(size_t n)
{
	return n/ 2;
}

template<typename T, size_t n>
void MaxHeapIFY(T(*arr)[n], size_t Largest, size_t sz = n)
{
	int parent;
	do
	{
		size_t left = Left(Largest);
		size_t right = Right(Largest);
		parent = Largest;

		if (left <= sz && (*arr)[left] > (*arr)[Largest])
			Largest = left;
		if (right <= sz && (*arr)[right] > (*arr)[Largest])
			Largest = right;

	} while (Swap(arr, parent, Largest));
}

template<typename T, size_t n>
bool Swap(T(*arr)[n], size_t i, size_t Largest)
{
	if (i != Largest)
	{
		std::swap((*arr)[i], (*arr)[Largest]);
		return true;
	}
	return false;
}

template<typename T, size_t n>
void BuildMaxHeap(T(*arr)[n], int sz = n/2)
{
	for (; sz >= 0; --sz)
		MaxHeapIFY(arr, sz);
	//倒序遍历为什么呢？
}

template<typename T, size_t n>
void HeapSort(T(*arr)[n], int sz = n-1)
{
	for (int i = sz; i > 0;)
	{
		std::swap((*arr)[i--], (*arr)[0]);
		MaxHeapIFY(arr, 0, i);
	}
}

int main()
{
	int arr1[] = { 11, 21, 13, 42, 12, 16, 27 };
	BuildMaxHeap(&arr1);//建立最大堆
	HeapSort(&arr1);//排序最大堆
	return 0;
}
